package org.algorithm.biubiu.wheel_1.BFS算法;

import org.algorithm.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author jzx
 * @date 2022/5/19
 * https://leetcode.cn/problems/same-tree/
 */
public class 相同的树 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if(p == null) return false;
        if(q == null) return false;
        boolean res = true;
        Queue<TreeNode> root1 = new LinkedList();
        root1.add(p);
        Queue<TreeNode> root2 = new LinkedList();
        root2.add(q);
        while(!root1.isEmpty()&&!root2.isEmpty()){
            int sz1 = root1.size();
            int sz2 = root2.size();
            if(sz1!=sz2){
                res = false;
                return res;
            }
            //
            for(int i = 0; i<sz1;i++){
                TreeNode node1 = root1.poll();
                TreeNode node2 = root2.poll();
                if(node1.val!=node2.val){
                    res = false;
                    return res;
                }
                if(node1.left!=null && node2.left!=null && node1.left.val ==node2.left.val){
                    root1.add(node1.left);
                    root2.add(node2.left);
                }else{
                    if(node1.left!=null || node2.left!=null){
                        res = false;
                        return res;
                    }
                }
                if(node1.right!=null && node2.right!=null && node1.right.val ==node2.right.val ){
                    root1.add(node1.right);
                    root2.add(node2.right);
                }else{
                    if(node1.right!=null || node2.right!=null){
                        res = false;
                        return res;
                    }

                }
            }

        }
        return res;
    }

    public boolean isSameTree1(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if(p==null) return false;
        if(q==null) return false;


        if(p.val==q.val){
            return  isSameTree1(p.left,q.left) && isSameTree(p.right,q.right);
        }
        return false;
    }
}
